package com.leetcode.algorithm.y22.m07;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * 692. 前K个高频单词
 * 
 * https://leetcode.cn/problems/top-k-frequent-words/
 * 
 * @author jie.deng
 *
 */
class Question0692Solution01 {

	public List<String> topKFrequent(String[] words, int k) {
		Map<String, Integer> cntMap = new HashMap<>();
		for (String word : words) {
			Integer cnt = cntMap.get(word);
			cntMap.put(word, cnt == null ? 1 : cnt.intValue() + 1);
		}
		Map<Integer, List<String>> wordsMap = new TreeMap<>((a, b) -> b - a);
		for (Map.Entry<String, Integer> entry : cntMap.entrySet()) {
			String word = entry.getKey();
			Integer cnt = entry.getValue();
			List<String> list = wordsMap.get(cnt);
			if (list == null) {
				list = new ArrayList<>();
				wordsMap.put(cnt, list);
			}
			list.add(word);
		}

		List<String> retList = new ArrayList<>();
		for (Map.Entry<Integer, List<String>> entry : wordsMap.entrySet()) {
			List<String> list = entry.getValue();
			Collections.sort(list);
			if (list.size() < k - retList.size()) {
				retList.addAll(list);
			} else {
				retList.addAll(list.subList(0, k - retList.size()));
				break;
			}
		}

		return retList;
	}

}